package com.francis;

import java.util.Arrays;

/**
 * 归并排序
 * @author francis
 * @create 2018-03-07 0:14
 **/
public class MergeSort {

    /**
     * 归并排序，思路就是分治，拆解成左右两个数组进行排序，再合并起来进行排序，算法时间复杂度为O(n*log(n))
     * @param array 需要排序的数组
     * @param start 本次排序起始的index
     * @param middle 本次排序中间的index
     * @param last 本次排序最后的index
     */
    public static void sort(int[] array, int start, int middle, int last) {
        if(middle < start || last < middle || array == null || array.length <= last) {
            throw new IllegalArgumentException("argument should matches: array is not null && middle <= start <= last < array.length!");
        }

        if(middle - start > 1) {
            sort(array, start, (middle + start) / 2, middle);
        }

        if(last - middle > 1) {
            sort(array, middle, (middle + last) / 2, last);
        }

        int[] leftArray = new int[middle - start];
        for(int k = 0; k < leftArray.length; k++) {
            leftArray[k] = array[k + start];
        }

        int[] rightArray = new int[last - middle + 1];
        for(int k = 0; k < rightArray.length; k++) {
            rightArray[k] = array[k + middle];
        }

        int i = 0, j = 0, x = start;

        while(i < leftArray.length || j < rightArray.length) {
            if(i >= leftArray.length) {
                while(j < rightArray.length) {
                    array[x++] = rightArray[j++];
                }
                continue;
            }

            if(j >= rightArray.length) {
                while(i < leftArray.length) {
                    array[x++] = leftArray[i++];
                }
                continue;
            }

            if(leftArray[i] <= rightArray[j]) {
                array[x++] = leftArray[i++];
            } else {
                array[x++] = rightArray[j++];
            }
        }
    }


    public static void main(String[] args) {
        int[] testArray = {9,10,3,2,4,5,1,6,7,8};
        sort(testArray, 0, testArray.length / 2, testArray.length - 1);
        System.out.println(Arrays.toString(testArray));
    }

}
